# -*- coding: utf-8 -*-
# 给定一个单词数组和一个长度 maxWidth，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本
# 你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符
# 要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数
# 文本的最后一行应为左对齐，且单词之间不插入额外的空格

# 说明:
# 单词是指由非空格字符组成的字符序列
# 每个单词的长度大于 0，小于等于 maxWidth
# 输入单词数组 words 至少包含一个单词

# 示例:
# 输入:
# words = ["This", "is", "an", "example", "of", "text", "justification."]
# maxWidth = 16
# 输出:
# [
#    "This    is    an",
#    "example  of text",
#    "justification.  "
# ]

# 示例 2:
# 输入:
# words = ["What","must","be","acknowledgment","shall","be"]
# maxWidth = 16
# 输出:
# [
#   "What   must   be",
#   "acknowledgment  ",
#   "shall be        "
# ]
# 解释: 注意最后一行的格式应为 "shall be    " 而不是 "shall     be",
#      因为最后一行应为左对齐，而不是左右两端对齐。       
#      第二行同样为左对齐，这是因为这行只包含一个单词

# 示例 3:
# 输入:
# words = ["Science","is","what","we","understand","well","enough","to","explain",
#          "to","a","computer.","Art","is","everything","else","we","do"]
# maxWidth = 20
# 输出:
# [
#   "Science  is  what we",
#   "understand      well",
#   "enough to explain to",
#   "a  computer.  Art is",
#   "everything  else  we",
#   "do                  "
# ]









class Solution(object):
    def fullJustify(self, words, maxWidth):
        """
        :type words: List[str]
        :type maxWidth: int
        :rtype: List[str]
        """
        index = 0;
        width = maxWidth;
        map = [];
        while index < len(words):
            length = len(words[index]);
            if not map:
                map.append({"n" : 0, "left" : maxWidth});
            signal = map[-1];
            if signal["left"] - length - (signal["n"] - 1) > 0:
                signal["n"] += 1;
                signal["left"] -= length;
            else:
                map.append({"n" : 0, "left" : maxWidth});
                continue;
            index += 1;

        rtn = [];
        index = 0;
        for i in range(len(map) - 1):
            it = map[i];
            signal = "";
            for i in range(it["n"]):
                signal += words[index];
                if it["n"] > 1 and i != it["n"] - 1:
                    empty = (it["left"] // (it["n"] - 1));
                    if it["left"] % (it["n"] - 1) > i:
                        empty += 1;
                    signal += " " * empty;
                index += 1;
            signal += " " * (maxWidth - len(signal));
            rtn.append(signal);

        signal = "";
        while index < len(words):
            signal += words[index];
            if maxWidth - len(signal) > 0:
                signal += " ";
            index += 1;
        signal += " " * (maxWidth - len(signal));
        rtn.append(signal);

        return rtn;

# 更加简短的书写方法
class Solution(object):
    def fullJustify(self, words, maxWidth):
        """
        :type words: List[str]
        :type maxWidth: int
        :rtype: List[str]
        """
        rtn = [];
        line_words = [];
        line_alpha_length = 0;

        for word in words:
            if len(word) + len(line_words) + line_alpha_length > maxWidth:
                for i in range(maxWidth - line_alpha_length):
                    line_words[i % (len(line_words) - 1 or 1)] += " ";
                rtn.append("".join(line_words));
                line_words = [word];
                line_alpha_length = len(word);
            else:
                line_words.append(word);
                line_alpha_length += len(word);

        rtn.append(" ".join(line_words).ljust(maxWidth, " "));
        return rtn;


t = Solution();
print t.fullJustify(["This", "is", "an", "example", "of", "text", "justification."], 16);
print t.fullJustify(["What","must","be","acknowledgment","shall","be"], 16);
print t.fullJustify(["Science","is","what","we","understand","well","enough","to","explain", "to","a","computer.","Art","is","everything","else","we","do"], 20);
